/**
 * class Node {
 * 		construct(val){
 * 			this.value: val;
 * 	 		this.next: null;
 * 		}
 * }
 */
class Node {
  constructor(val) {
    this.value = val;
    this.next = null;
  }
}

// 链表
class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0; // length 同数组 length 与下标关系
  }

  // 追加元素
  append(element) {
    let node = new Node(element);
    let current = null; // 指针？

    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }

  // 任意位置插入元素
  insert(position, element) {
    if (position >= 0 && position <= this.length) {
      let node = new Node(element);
      let current = this.head;
      let previous = null;
      let index = 0;
      if (position === 0) {
        this.head = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;
      }
      this.length++;
      return true;
    }
    return false;
  }

  // 移除指定位置元素
  removeAt(position) {
    if (position > -1 && position < length) {
      let current = this.head;
      let previous = null;
      let index = 0;
      if (position === 0) {
        this.head = current.next;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      this.length--;
      return current.element;
    }
    return null;
  }

  // 寻找元素下标
  findIndex(element) {
    let current = this.head;
    let index = -1;
    while (current) {
      if (element === current.element) {
        return index + 1;
      }
      index++;
      current = current.next;
    }

    return -1;
  }

  // 删除指定文档
  remove(element) {
    let index = this.findIndex(element);
    return removeAt(index);
  }

  isEmpty() {
    return !this.length;
  }

  size() {
    return this.length;
  }

  // 输出字符串
  toString() {
    let current = this.head;
    let string = "";
    while (current) {
      string += ` ${current.value}`;
      current = current.next;
    }
    return string;
  }

  reverseLink() {
    var pre = null;
    var nextCur = null;
    var head = this.head;
    while (head) {
      nextCur = head.next;
      head.next = pre;
      pre = head;
      head = nextCur;
    }
    this.head = pre;
    return this.head;
  }
}

var ll = new LinkedList();
console.log(ll);
ll.append(2);
ll.append(6);
ll.append(24);
ll.append(152);

ll.insert(3, 18);

console.log(ll.toString());

ll.reverseLink();

console.log(ll.toString());

// 其他解法：
// 迭代法： 同上面的双指针
var reverseList1 = function(head) {
  let [prev, curr] = [null, head];
  while (curr) {
    [curr.next, prev, curr] = [prev, curr, curr.next];
  }
  return prev;
};

//  递归：
var reverseList2 = function(head) {
  if (!head || !head.next) return head;
  let next = head.next;
  let reverseHead = reverseList2(next);
  head.next = null;
  next.next = head;
  return reverseHead;
};

var reverseList3 = function(head) {
  function reverse(prev, curr) {
    if (!curr) return prev;
    let tmp = curr.next;
    curr.next = prev;
    return reverse(curr, tmp);
  }

  return reverse(null, head);
};
